//https://leetcode.cn/problems/split-array-largest-sum/description/?envType=daily-question&envId=2024-01-21


class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, LLONG_MAX));
        vector<long long> sub(n + 1, 0);
        for(int i = 0; i < n; ++i)
            sub[i + 1] = sub[i] + nums[i];
        dp[0][0] = 0;
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= min(i, k); ++j)
                for(int m = 0; m < i; ++m)
                    dp[i][j] = min(dp[i][j], max(dp[m][j - 1], sub[i] - sub[m]));
        return (int)dp[n][k];
    }
};